//
// Created by DengLibin on 2019/1/23 0023.
//
#include <iostream>
using  namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
/**
       是否是叶子节点
   */
bool isYeZi(TreeNode * root){
    if(root == NULL){
        return false;
    }
    return root->left == NULL && root->right == NULL;
}
void getSum(TreeNode * root, int sum, int targetSum, bool * flag){
    if(isYeZi(root)){
        //当累加到叶子节点时判断是否和指定的和相等
        if(sum + root->val == targetSum && (*flag) == false){
            *flag = true;
        }
        return;
    }
    getSum(root->left, sum+root->val, targetSum,flag);
    getSum(root->right, sum+root->val, targetSum,flag);

}
/**
 * 是否存在路径总和等于给定的值 方法一
 * @param root
 * @param sum
 * @return
 */
bool hasPathSum(TreeNode* root, int sum) {
    bool  flag = false;
    if(root == NULL){
        return false;
    }
    getSum(root,0,sum,&flag);
    return flag;
}
/**
 * 是否存在路径总和等于给定的值 方法二
 * @param root
 * @param sum
 * @return
 */
bool hasPathSum2(TreeNode* root, int sum) {
    if(root == NULL){
        return false;
    }
    if(isYeZi(root)){
        return root->val - sum == 0;
    }
    return hasPathSum2(root->left, sum - root->val) || hasPathSum2(root->right,sum - root->val);

}



int main73(){
    TreeNode node1 = {3};
    TreeNode node2 = {9};
    TreeNode node3 = {20};
    node1.left = &node2;
    node1.right = &node3;
    TreeNode node5 = {7};
    TreeNode node6 = {15};
    node3.left = &node5;
    node3.right = &node6;

    cout<<hasPathSum(&node1,30)<<endl;
    return 0;
}